package 热题100.链表.合并k个升序链表_23_困难;
import 链表.删除链表的倒数第N个结点_19.Solution.ListNode;

import java.util.List;
import java.util.PriorityQueue;

/*
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：

输入：lists = []
输出：[]
示例 3：

输入：lists = [[]]
输出：[]

思路：
    一：先实现两个链表合并，然后遍历链表数组轮着合并(朴素做法)
    二：我们需要维护当前每个链表没有被合并的元素的最前面一个，k 个链表就最多有 k 个满足这样条件的元素，
    每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候，我们可以用优先队列来优化这个过程。

* */
public class Solution {
    public static void main(String[] args) {
        ListNode[] headB = new ListNode[3];
        ListNode[] headA = new ListNode[4];
        ListNode[] headC = new ListNode[2];

        headA[3] = new ListNode(4,null);
        headA[2] = new ListNode(3,headA[3]);
        headA[1] = new ListNode(2,headA[2]);
        headA[0] = new ListNode(1,headA[1]);

        headB[2] = new ListNode(4,null);
        headB[1] = new ListNode(3,headB[2]);
        headB[0] = new ListNode(1,headB[1]);

        headC[1] = new ListNode(6, null);
        headC[0] = new ListNode(2, headC[1]);

        ListNode[] lists = {headA[0], headB[0], headC[0]};
        ListNode ans = mergeKLists(lists);
        while (ans != null){
            System.out.println(ans.val);
            ans = ans.next;
        }
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        ListNode demmy = new ListNode();
        ListNode cur = demmy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(((o1, o2) -> {return o1.val - o2.val;}));
        // 把每个链表的头节点放入优先队列进行排序
        for (ListNode node : lists){
            if (node != null){
                pq.offer(node);
            }
        }

        while (!pq.isEmpty()){
            // 将节点拿出来记录，并推到下一个节点
            ListNode temp = pq.poll();
            cur.next = temp;
            cur = cur.next;
            temp = temp.next;
            if (temp != null){
                pq.offer(temp);
            }
        }
        return demmy.next;
    }

/*    public static ListNode mergeKLists(ListNode[] lists) {
        int length = lists.length;
        if (length == 1){
            return lists[0];
        }
        if(length < 1){
            return null;
        }
        ListNode temp = lists[0];
        // 循环合并
        for (int i = 1; i < length; i ++){
            temp = merge(temp, lists[i]);
        }
        return temp;
    }*/

    //合并两个链表
    public static ListNode merge(ListNode a, ListNode b){
        ListNode begin = new ListNode(-1), ans = begin;
        if (a == null && b == null){
            return null;
        }
        while (a != null && b != null){
            if (a.val <= b.val){
                begin.next = a;
                a = a.next;
            } else {
                begin.next = b;
                b = b.next;
            }
            begin = begin.next;
        }
        if (a != null) begin.next = a;
        if (b != null) begin.next = b;
        return ans.next;
    }
}
